#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

// 17. 电话号码的字母组合
// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

class Solution {
private:
    // 数字字符到字符串的映射
    const string letterMap[10] = {
            " ",    //0
            "",     //1
            "abc",  //2
            "def",  //3
            "ghi",  //4
            "jkl",  //5
            "mno",  //6
            "pqrs", //7
            "tuv",  //8
            "wxyz"  //9
    };
    vector<string> res;
    // s中保存了此时从 digits[0...index-1]翻译得到的一个字母字符串
    // 寻找和digits[index]匹配的字母，获得digits[0...index]翻译得到的解
    // digits: 数字字符串 index: 每次调用该函数时，只处理该数字字符串的1位，这一位的索引是index
    // s：在每次处理一个字符时，之前的数字已经进行了一些转换，之前的数字转换的字符串存在s中
    void findCombination(const string &digits, int index, const string &s) {
        if(index == digits.size()) {
            // 此时获得的s是这个问题的一个解。保存s
            res.push_back(s);
            return;
        }
        char c = digits[index]; // 当前处理的字符
        assert(c >= '0' && c <= '9' && c != '1');

        string letters = letterMap[c - '0'];    // 获得当前数字字符对应的字母是哪些
        for(int i = 0; i < letters.size(); i++)
            // 把letters的第i个字符放在s后面，继续向下寻找第index+1个数字字符
            findCombination(digits, index+1, s + letters[i]);
    }
public:
    vector<string> letterCombinations(string digits) {
        res.clear();
//        if(digits == "")
        if(digits.empty())
            return res;
        findCombination(digits, 0, "");
        return res;
    }
};
int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
